package org.example.two.sort;

import org.example.two.Example;

/**
 * 自底向上的归并排序
 */
public class MergeBU extends Example {
    private Comparable[] aux;

    @Override
    public void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        for (int sz = 1; sz < a.length; sz+=sz) {
            for (int lo = 0; lo < a.length-sz; lo +=(sz+sz)) {
                marge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,a.length-1));
            }
        }
    }

    public void marge(Comparable[] a , int lo , int mid , int hi ){
        System.arraycopy(a,lo,aux,lo,hi-lo+1);
        int k = lo;
        int j = mid+1;
        for (int i = lo; i <= hi ; i++) {
            if (k>mid){
                a[i] = aux[j++];
            }else if (j>hi){
                a[i] = aux[k++];
            }else if (les(aux[j],aux[k])){
                a[i] = aux[j++];
            }else {
                a[i] = aux[k++];
            }
        }
    }
}
